<!doctype html>

<html>
<head>
  <link rel="shortcut icon" href="static/images/favicon.ico" type="image/x-icon">
  <title>rangeset.js (Closure Library API Documentation - JavaScript)</title>
  <link rel="stylesheet" href="static/css/base.css">
  <link rel="stylesheet" href="static/css/doc.css">
  <link rel="stylesheet" href="static/css/sidetree.css">
  <link rel="stylesheet" href="static/css/prettify.css">

  <script>
     var _staticFilePath = "static/";
     var _typeTreeName = "goog";
     var _fileTreeName = "Source";
  </script>

  <script src="static/js/doc.js">
  </script>


  <meta charset="utf8">
</head>

<body onload="grokdoc.onLoad();">

<div id="header">
  <div class="g-section g-tpl-50-50 g-split">
    <div class="g-unit g-first">
      <a id="logo" href="index.html">Closure Library API Documentation</a>
    </div>

    <div class="g-unit">
      <div class="g-c">
        <strong>Go to class or file:</strong>
        <input type="text" id="ac">
      </div>
    </div>
  </div>
</div>

<div class="clear"></div>

<h2><a href="closure_goog_math_rangeset.js.html">rangeset.js</a></h2>

<pre class="prettyprint lang-js">
<a name="line1"></a>// Copyright 2009 The Closure Library Authors. All Rights Reserved.
<a name="line2"></a>//
<a name="line3"></a>// Licensed under the Apache License, Version 2.0 (the &quot;License&quot;);
<a name="line4"></a>// you may not use this file except in compliance with the License.
<a name="line5"></a>// You may obtain a copy of the License at
<a name="line6"></a>//
<a name="line7"></a>//      http://www.apache.org/licenses/LICENSE-2.0
<a name="line8"></a>//
<a name="line9"></a>// Unless required by applicable law or agreed to in writing, software
<a name="line10"></a>// distributed under the License is distributed on an &quot;AS-IS&quot; BASIS,
<a name="line11"></a>// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
<a name="line12"></a>// See the License for the specific language governing permissions and
<a name="line13"></a>// limitations under the License.
<a name="line14"></a>
<a name="line15"></a>/**
<a name="line16"></a> * @fileoverview A RangeSet is a structure that manages a list of ranges.
<a name="line17"></a> * Numeric ranges may be added and removed from the RangeSet, and the set may
<a name="line18"></a> * be queried for the presence or absence of individual values or ranges of
<a name="line19"></a> * values.
<a name="line20"></a> *
<a name="line21"></a> * This may be used, for example, to track the availability of sparse elements
<a name="line22"></a> * in an array without iterating over the entire array.
<a name="line23"></a> *
<a name="line24"></a> * @author brenneman@google.com (Shawn Brenneman)
<a name="line25"></a> */
<a name="line26"></a>
<a name="line27"></a>goog.provide(&#39;goog.math.RangeSet&#39;);
<a name="line28"></a>
<a name="line29"></a>goog.require(&#39;goog.array&#39;);
<a name="line30"></a>goog.require(&#39;goog.iter.Iterator&#39;);
<a name="line31"></a>goog.require(&#39;goog.iter.StopIteration&#39;);
<a name="line32"></a>goog.require(&#39;goog.math.Range&#39;);
<a name="line33"></a>
<a name="line34"></a>
<a name="line35"></a>
<a name="line36"></a>/**
<a name="line37"></a> * Constructs a new RangeSet, which can store numeric ranges.
<a name="line38"></a> *
<a name="line39"></a> * Ranges are treated as half-closed: that is, they are exclusive of their end
<a name="line40"></a> * value [start, end).
<a name="line41"></a> *
<a name="line42"></a> * New ranges added to the set which overlap the values in one or more existing
<a name="line43"></a> * ranges will be merged.
<a name="line44"></a> *
<a name="line45"></a> * @constructor
<a name="line46"></a> */
<a name="line47"></a>goog.math.RangeSet = function() {
<a name="line48"></a>  /**
<a name="line49"></a>   * A sorted list of ranges that represent the values in the set.
<a name="line50"></a>   * @type {!Array.&lt;!goog.math.Range&gt;}
<a name="line51"></a>   * @private
<a name="line52"></a>   */
<a name="line53"></a>  this.ranges_ = [];
<a name="line54"></a>};
<a name="line55"></a>
<a name="line56"></a>
<a name="line57"></a>if (goog.DEBUG) {
<a name="line58"></a>  /**
<a name="line59"></a>   * @return {string} A debug string in the form [[1, 5], [8, 9], [15, 30]].
<a name="line60"></a>   * @override
<a name="line61"></a>   */
<a name="line62"></a>  goog.math.RangeSet.prototype.toString = function() {
<a name="line63"></a>    return &#39;[&#39; + this.ranges_.join(&#39;, &#39;) + &#39;]&#39;;
<a name="line64"></a>  };
<a name="line65"></a>}
<a name="line66"></a>
<a name="line67"></a>
<a name="line68"></a>/**
<a name="line69"></a> * Compares two sets for equality.
<a name="line70"></a> *
<a name="line71"></a> * @param {goog.math.RangeSet} a A range set.
<a name="line72"></a> * @param {goog.math.RangeSet} b A range set.
<a name="line73"></a> * @return {boolean} Whether both sets contain the same values.
<a name="line74"></a> */
<a name="line75"></a>goog.math.RangeSet.equals = function(a, b) {
<a name="line76"></a>  // Fast check for object equality. Also succeeds if a and b are both null.
<a name="line77"></a>  return a == b || !!(a &amp;&amp; b &amp;&amp; goog.array.equals(a.ranges_, b.ranges_,
<a name="line78"></a>      goog.math.Range.equals));
<a name="line79"></a>};
<a name="line80"></a>
<a name="line81"></a>
<a name="line82"></a>/**
<a name="line83"></a> * @return {!goog.math.RangeSet} A new RangeSet containing the same values as
<a name="line84"></a> *      this one.
<a name="line85"></a> */
<a name="line86"></a>goog.math.RangeSet.prototype.clone = function() {
<a name="line87"></a>  var set = new goog.math.RangeSet();
<a name="line88"></a>
<a name="line89"></a>  for (var i = this.ranges_.length; i--;) {
<a name="line90"></a>    set.ranges_[i] = this.ranges_[i].clone();
<a name="line91"></a>  }
<a name="line92"></a>
<a name="line93"></a>  return set;
<a name="line94"></a>};
<a name="line95"></a>
<a name="line96"></a>
<a name="line97"></a>/**
<a name="line98"></a> * Adds a range to the set. If the new range overlaps existing values, those
<a name="line99"></a> * ranges will be merged.
<a name="line100"></a> *
<a name="line101"></a> * @param {goog.math.Range} a The range to add.
<a name="line102"></a> */
<a name="line103"></a>goog.math.RangeSet.prototype.add = function(a) {
<a name="line104"></a>  if (a.end &lt;= a.start) {
<a name="line105"></a>    // Empty ranges are ignored.
<a name="line106"></a>    return;
<a name="line107"></a>  }
<a name="line108"></a>
<a name="line109"></a>  a = a.clone();
<a name="line110"></a>
<a name="line111"></a>  // Find the insertion point.
<a name="line112"></a>  for (var i = 0, b; b = this.ranges_[i]; i++) {
<a name="line113"></a>    if (a.start &lt;= b.end) {
<a name="line114"></a>      a.start = Math.min(a.start, b.start);
<a name="line115"></a>      break;
<a name="line116"></a>    }
<a name="line117"></a>  }
<a name="line118"></a>
<a name="line119"></a>  var insertionPoint = i;
<a name="line120"></a>
<a name="line121"></a>  for (; b = this.ranges_[i]; i++) {
<a name="line122"></a>    if (a.end &lt; b.start) {
<a name="line123"></a>      break;
<a name="line124"></a>    }
<a name="line125"></a>    a.end = Math.max(a.end, b.end);
<a name="line126"></a>  }
<a name="line127"></a>
<a name="line128"></a>  this.ranges_.splice(insertionPoint, i - insertionPoint, a);
<a name="line129"></a>};
<a name="line130"></a>
<a name="line131"></a>
<a name="line132"></a>/**
<a name="line133"></a> * Removes a range of values from the set.
<a name="line134"></a> *
<a name="line135"></a> * @param {goog.math.Range} a The range to remove.
<a name="line136"></a> */
<a name="line137"></a>goog.math.RangeSet.prototype.remove = function(a) {
<a name="line138"></a>  if (a.end &lt;= a.start) {
<a name="line139"></a>    // Empty ranges are ignored.
<a name="line140"></a>    return;
<a name="line141"></a>  }
<a name="line142"></a>
<a name="line143"></a>  // Find the insertion point.
<a name="line144"></a>  for (var i = 0, b; b = this.ranges_[i]; i++) {
<a name="line145"></a>    if (a.start &lt; b.end) {
<a name="line146"></a>      break;
<a name="line147"></a>    }
<a name="line148"></a>  }
<a name="line149"></a>
<a name="line150"></a>  if (!b || a.end &lt; b.start) {
<a name="line151"></a>    // The range being removed doesn&#39;t overlap any existing range. Exit early.
<a name="line152"></a>    return;
<a name="line153"></a>  }
<a name="line154"></a>
<a name="line155"></a>  var insertionPoint = i;
<a name="line156"></a>
<a name="line157"></a>  if (a.start &gt; b.start) {
<a name="line158"></a>    // There is an overlap with the nearest range. Modify it accordingly.
<a name="line159"></a>    insertionPoint++;
<a name="line160"></a>
<a name="line161"></a>    if (a.end &lt; b.end) {
<a name="line162"></a>      goog.array.insertAt(this.ranges_,
<a name="line163"></a>                          new goog.math.Range(a.end, b.end),
<a name="line164"></a>                          insertionPoint);
<a name="line165"></a>    }
<a name="line166"></a>    b.end = a.start;
<a name="line167"></a>  }
<a name="line168"></a>
<a name="line169"></a>  for (i = insertionPoint; b = this.ranges_[i]; i++) {
<a name="line170"></a>    b.start = Math.max(a.end, b.start);
<a name="line171"></a>    if (a.end &lt; b.end) {
<a name="line172"></a>      break;
<a name="line173"></a>    }
<a name="line174"></a>  }
<a name="line175"></a>
<a name="line176"></a>  this.ranges_.splice(insertionPoint, i - insertionPoint);
<a name="line177"></a>};
<a name="line178"></a>
<a name="line179"></a>
<a name="line180"></a>/**
<a name="line181"></a> * Determines whether a given range is in the set. Only succeeds if the entire
<a name="line182"></a> * range is available.
<a name="line183"></a> *
<a name="line184"></a> * @param {goog.math.Range} a The query range.
<a name="line185"></a> * @return {boolean} Whether the entire requested range is set.
<a name="line186"></a> */
<a name="line187"></a>goog.math.RangeSet.prototype.contains = function(a) {
<a name="line188"></a>  if (a.end &lt;= a.start) {
<a name="line189"></a>    return false;
<a name="line190"></a>  }
<a name="line191"></a>
<a name="line192"></a>  for (var i = 0, b; b = this.ranges_[i]; i++) {
<a name="line193"></a>    if (a.start &lt; b.end) {
<a name="line194"></a>      if (a.end &gt;= b.start) {
<a name="line195"></a>        return goog.math.Range.contains(b, a);
<a name="line196"></a>      }
<a name="line197"></a>      break;
<a name="line198"></a>    }
<a name="line199"></a>  }
<a name="line200"></a>  return false;
<a name="line201"></a>};
<a name="line202"></a>
<a name="line203"></a>
<a name="line204"></a>/**
<a name="line205"></a> * Determines whether a given value is set in the RangeSet.
<a name="line206"></a> *
<a name="line207"></a> * @param {number} value The value to test.
<a name="line208"></a> * @return {boolean} Whether the given value is in the set.
<a name="line209"></a> */
<a name="line210"></a>goog.math.RangeSet.prototype.containsValue = function(value) {
<a name="line211"></a>  for (var i = 0, b; b = this.ranges_[i]; i++) {
<a name="line212"></a>    if (value &lt; b.end) {
<a name="line213"></a>      if (value &gt;= b.start) {
<a name="line214"></a>        return true;
<a name="line215"></a>      }
<a name="line216"></a>      break;
<a name="line217"></a>    }
<a name="line218"></a>  }
<a name="line219"></a>  return false;
<a name="line220"></a>};
<a name="line221"></a>
<a name="line222"></a>
<a name="line223"></a>/**
<a name="line224"></a> * Returns the union of this RangeSet with another.
<a name="line225"></a> *
<a name="line226"></a> * @param {goog.math.RangeSet} set Another RangeSet.
<a name="line227"></a> * @return {!goog.math.RangeSet} A new RangeSet containing all values from
<a name="line228"></a> *     either set.
<a name="line229"></a> */
<a name="line230"></a>goog.math.RangeSet.prototype.union = function(set) {
<a name="line231"></a>  // TODO(brenneman): A linear-time merge would be preferable if it is ever a
<a name="line232"></a>  // bottleneck.
<a name="line233"></a>  set = set.clone();
<a name="line234"></a>
<a name="line235"></a>  for (var i = 0, a; a = this.ranges_[i]; i++) {
<a name="line236"></a>    set.add(a);
<a name="line237"></a>  }
<a name="line238"></a>
<a name="line239"></a>  return set;
<a name="line240"></a>};
<a name="line241"></a>
<a name="line242"></a>
<a name="line243"></a>/**
<a name="line244"></a> * Subtracts the ranges of another set from this one, returning the result
<a name="line245"></a> * as a new RangeSet.
<a name="line246"></a> *
<a name="line247"></a> * @param {!goog.math.RangeSet} set The RangeSet to subtract.
<a name="line248"></a> * @return {!goog.math.RangeSet} A new RangeSet containing all values in this
<a name="line249"></a> *     set minus the values of the input set.
<a name="line250"></a> */
<a name="line251"></a>goog.math.RangeSet.prototype.difference = function(set) {
<a name="line252"></a>  var ret = this.clone();
<a name="line253"></a>
<a name="line254"></a>  for (var i = 0, a; a = set.ranges_[i]; i++) {
<a name="line255"></a>    ret.remove(a);
<a name="line256"></a>  }
<a name="line257"></a>
<a name="line258"></a>  return ret;
<a name="line259"></a>};
<a name="line260"></a>
<a name="line261"></a>
<a name="line262"></a>/**
<a name="line263"></a> * Intersects this RangeSet with another.
<a name="line264"></a> *
<a name="line265"></a> * @param {goog.math.RangeSet} set The RangeSet to intersect with.
<a name="line266"></a> * @return {!goog.math.RangeSet} A new RangeSet containing all values set in
<a name="line267"></a> *     both this and the input set.
<a name="line268"></a> */
<a name="line269"></a>goog.math.RangeSet.prototype.intersection = function(set) {
<a name="line270"></a>  if (this.isEmpty() || set.isEmpty()) {
<a name="line271"></a>    return new goog.math.RangeSet();
<a name="line272"></a>  }
<a name="line273"></a>
<a name="line274"></a>  return this.difference(set.inverse(this.getBounds()));
<a name="line275"></a>};
<a name="line276"></a>
<a name="line277"></a>
<a name="line278"></a>/**
<a name="line279"></a> * Creates a subset of this set over the input range.
<a name="line280"></a> *
<a name="line281"></a> * @param {goog.math.Range} range The range to copy into the slice.
<a name="line282"></a> * @return {!goog.math.RangeSet} A new RangeSet with a copy of the values in the
<a name="line283"></a> *     input range.
<a name="line284"></a> */
<a name="line285"></a>goog.math.RangeSet.prototype.slice = function(range) {
<a name="line286"></a>  var set = new goog.math.RangeSet();
<a name="line287"></a>  if (range.start &gt;= range.end) {
<a name="line288"></a>    return set;
<a name="line289"></a>  }
<a name="line290"></a>
<a name="line291"></a>  for (var i = 0, b; b = this.ranges_[i]; i++) {
<a name="line292"></a>    if (b.end &lt;= range.start) {
<a name="line293"></a>      continue;
<a name="line294"></a>    }
<a name="line295"></a>    if (b.start &gt; range.end) {
<a name="line296"></a>      break;
<a name="line297"></a>    }
<a name="line298"></a>
<a name="line299"></a>    set.add(new goog.math.Range(Math.max(range.start, b.start),
<a name="line300"></a>                                Math.min(range.end, b.end)));
<a name="line301"></a>  }
<a name="line302"></a>
<a name="line303"></a>  return set;
<a name="line304"></a>};
<a name="line305"></a>
<a name="line306"></a>
<a name="line307"></a>/**
<a name="line308"></a> * Creates an inverted slice of this set over the input range.
<a name="line309"></a> *
<a name="line310"></a> * @param {goog.math.Range} range The range to copy into the slice.
<a name="line311"></a> * @return {!goog.math.RangeSet} A new RangeSet containing inverted values from
<a name="line312"></a> *     the original over the input range.
<a name="line313"></a> */
<a name="line314"></a>goog.math.RangeSet.prototype.inverse = function(range) {
<a name="line315"></a>  var set = new goog.math.RangeSet();
<a name="line316"></a>
<a name="line317"></a>  set.add(range);
<a name="line318"></a>  for (var i = 0, b; b = this.ranges_[i]; i++) {
<a name="line319"></a>    if (range.start &gt;= b.end) {
<a name="line320"></a>      continue;
<a name="line321"></a>    }
<a name="line322"></a>    if (range.end &lt; b.start) {
<a name="line323"></a>      break;
<a name="line324"></a>    }
<a name="line325"></a>
<a name="line326"></a>    set.remove(b);
<a name="line327"></a>  }
<a name="line328"></a>
<a name="line329"></a>  return set;
<a name="line330"></a>};
<a name="line331"></a>
<a name="line332"></a>
<a name="line333"></a>/**
<a name="line334"></a> * @return {number} The sum of the lengths of ranges covered in the set.
<a name="line335"></a> */
<a name="line336"></a>goog.math.RangeSet.prototype.coveredLength = function() {
<a name="line337"></a>  return /** @type {number} */ (goog.array.reduce(
<a name="line338"></a>      this.ranges_,
<a name="line339"></a>      function(res, range) {
<a name="line340"></a>        return res + range.end - range.start;
<a name="line341"></a>      }, 0));
<a name="line342"></a>};
<a name="line343"></a>
<a name="line344"></a>
<a name="line345"></a>/**
<a name="line346"></a> * @return {goog.math.Range} The total range this set covers, ignoring any
<a name="line347"></a> *     gaps between ranges.
<a name="line348"></a> */
<a name="line349"></a>goog.math.RangeSet.prototype.getBounds = function() {
<a name="line350"></a>  if (this.ranges_.length) {
<a name="line351"></a>    return new goog.math.Range(this.ranges_[0].start,
<a name="line352"></a>                               goog.array.peek(this.ranges_).end);
<a name="line353"></a>  }
<a name="line354"></a>
<a name="line355"></a>  return null;
<a name="line356"></a>};
<a name="line357"></a>
<a name="line358"></a>
<a name="line359"></a>/**
<a name="line360"></a> * @return {boolean} Whether any ranges are currently in the set.
<a name="line361"></a> */
<a name="line362"></a>goog.math.RangeSet.prototype.isEmpty = function() {
<a name="line363"></a>  return this.ranges_.length == 0;
<a name="line364"></a>};
<a name="line365"></a>
<a name="line366"></a>
<a name="line367"></a>/**
<a name="line368"></a> * Removes all values in the set.
<a name="line369"></a> */
<a name="line370"></a>goog.math.RangeSet.prototype.clear = function() {
<a name="line371"></a>  this.ranges_.length = 0;
<a name="line372"></a>};
<a name="line373"></a>
<a name="line374"></a>
<a name="line375"></a>/**
<a name="line376"></a> * Returns an iterator that iterates over the ranges in the RangeSet.
<a name="line377"></a> *
<a name="line378"></a> * @param {boolean=} opt_keys Ignored for RangeSets.
<a name="line379"></a> * @return {!goog.iter.Iterator} An iterator over the values in the set.
<a name="line380"></a> */
<a name="line381"></a>goog.math.RangeSet.prototype.__iterator__ = function(opt_keys) {
<a name="line382"></a>  var i = 0;
<a name="line383"></a>  var list = this.ranges_;
<a name="line384"></a>
<a name="line385"></a>  var iterator = new goog.iter.Iterator();
<a name="line386"></a>  iterator.next = function() {
<a name="line387"></a>    if (i &gt;= list.length) {
<a name="line388"></a>      throw goog.iter.StopIteration;
<a name="line389"></a>    }
<a name="line390"></a>    return list[i++].clone();
<a name="line391"></a>  };
<a name="line392"></a>
<a name="line393"></a>  return iterator;
<a name="line394"></a>};
</pre>


</body>
</html>
